﻿#include <iostream>
#include <vector>
#include <queue>
#include <unordered_map>
#include <unordered_set>
using namespace std;

class Solution
{
    unordered_map<char, unordered_set<char>> edges; // 邻接表存储图
    unordered_map<char, int> in; // 统计入度
    bool check; // 检查边界情况
public:
    // LCR 114. 火星词典
    string alienOrder(vector<string>& words)
    {
        // 1、建表 + 初始化入度哈希表
        for (auto& s : words)
            for (auto ch : s)
                in[ch] = 0;

        int n = words.size();
        for (int i = 0; i < n; ++i)
        {
            for (int j = i + 1; j < n; ++j)
            {
                //cmp(words[i], words[j]);
                if (check)
                    return "";
            }
        }

        // 2、拓扑排序
        queue<char> q;
        for (pair<char, int> x : in)
            if (x.second == 0)
                q.push(x.first);

        string ret;
        while (q.size())
        {
            char t = q.front();
            q.pop();
            ret += t;

            for (auto ch : edges[t])
                if (--in[ch] == 0)
                    q.push(ch);
        }

        // 3、判断是否有环
        for (pair<char, int> x : in)
            if (x.second != 0)
                return "";
        return ret;
    }

    void cmp(const string& s1, const string& s2)
    {
        int n = min(s1.size(), s2.size());
        int i = 0;
        for (; i < n; ++i)
        {
            if (s1[i] != s2[i])
            {
                char a = s1[i], b = s2[i];
                if (!edges.count(a) || !edges[a].count(b))
                {
                    edges[a].insert(b);
                    in[b]++;
                }
                break;
            }
        }

        if (i == s2.size() && i < s1.size())
            check = true;
    }
};

int main()
{
    string res;
    vector<string> v{ {"wrt"},{"wrf"},{"er"},{"ett"},{"rftt"} };
    res = Solution().alienOrder(v);
    for (auto ch : res)
        cout << ch;
    cout << endl;
    return 0;
}